package org.example.myleet.p547;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    /**
     * 6 ms
     * BFS
     */
    public int findCircleNum(int[][] isConnected) {
        int circleCount = 0;
        int[] visited = new int[isConnected.length];
        //待搜索的队列
        Queue<Integer> citiesToBeVisited = new LinkedList<>();
        int unvisitedCity = 0;
        while (unvisitedCity >= 0) {
            //未查看的节点入待搜索的队列
            citiesToBeVisited.offer(unvisitedCity);
            //找到一个连通图
            ++circleCount;
            while (!citiesToBeVisited.isEmpty()) {
                //队列中已经入队的节点出列
                int curSize = citiesToBeVisited.size();
                for (int i=0; i<curSize; i++) {
                    int city = citiesToBeVisited.poll();
                    visited[city] = 1;
                    for (int j=0; j<isConnected[city].length; j++) {
                        if (visited[j] > 0) {
                            continue;
                        }
                        if (isConnected[city][j] > 0) {
                            //连通的城市加入待搜索的队列中
                            citiesToBeVisited.offer(j);
                        }
                    }
                }
            }
            //完成一个整个连通图的BFS搜索，获得一个连通图，接下来寻找另一个连通图
            unvisitedCity = -1;
            for (int i=1; i<visited.length; i++) {
                if (visited[i] < 1) {
                    //下一个连通图的起点
                    unvisitedCity = i;
                    break;
                }
            }
        }
        return circleCount;
    }
}
